A content addressable memory (CAM) device is a storage device that can be instructed to compare a specific pattern of comparand data with data stored in its associative CAM array. The entire CAM array, or segments thereof, are searched in parallel for a match with the comparand data. The CAM device typically indicates if a match occurs by asserting a match flag, and also typically indicates if multiple matches occur by asserting a multiple match flag. The CAM device can then be instructed to output the highest priority match address or index, data stored in one or more CAM cells at the matching address, and other status information including the match flags, a full flag, validity bits (e.g., skip and empty bits), and other status information.
CAM devices require a particular amount of time to perform a compare operation. This time includes the time to load and decode the compare instruction, the time to provide the comparand data to the CAM array, the time to perform the comparison operation within the CAM array, and the time to determine the highest priority matching location. Typical compare operation times range from approximately 25 ns (40 MHz) up to 125 to 300 ns. Compare operations have a direct correlation to search rates for the CAM device. It is generally desirable to increase the search rate of a CAM device so to increase the overall throughput of a system incorporating the CAM device.
Pipelining compare instructions to a particular CAM device has been used to increase the throughput of that CAM device. By pipelining compare instructions, the CAM device can run at its maximum sustained search rate over multiple periods of time. For example, if a CAM device can run at 40 MHz and perform one search per clock cycle (i.e., 40 MS/s or 40 million searches per second), then pipelining of the compare instruction will enable the CAM device to further increase the search rate at the expense of an initial cycle latency.
FIGS. 1 and 2 show another technique for increasing the search rate of a CAM device. In FIG. 1, a single CAM device has been replaced with a CAM system 100 that includes multiple CAM devices 107-110 that can increase the sustained search rate of CAM system 100 to approximately four times over that of a single CAM device (e.g., CAM device 107). For example, as shown in FIG. 2, if CAM device 107 has an individual maximum sustained search rate of 40 MS/s, then system 100 can increase the sustained search rate of system 100 to 160 MS/s. This is accomplished at the expense of adding three redundant CAM devices 108-110 each storing a redundant set of data, and by providing separate comparand data to each CAM device in successive clock cycles. As shown in FIG. 2, CAM device 107 will receive a first compare instruction (CMP1) and first comparand data during a first system clock cycle, CAM device 108 will receive a second compare instruction (CMP2) and second comparand data during a second system clock cycle, CAM device 109 will receive a third compare instruction (CMP3) and third comparand data during a third system clock cycle, and CAM device 110 will receive a fourth compare instruction (CMP4) and fourth comparand data during a fourth system clock cycle. While the system clock runs at 160 MHz, each individual CAM device runs at 40 MHz and typically receives a 40 MHz clock signal in addition to the 160 MHz system clock (or a logical combination of the two clocks).
As each CAM device has an individual search rate of 40 MS/s, each CAM device will output to OBUS 104 the matching address of any matching location in its CAM array approximately five cycles after receiving its compare instruction and comparand data. Thus, after an initial lag period of approximately 25 ns, the sustained search rate will be approximately 160 MS/s starting at cycle T4. This increased sustained search rate, however, is achieved at the expense of adding three redundant CAM device 108-110 and control logic (not shown) necessary to ensure that each CAM device is selected in at the appropriate time to receive the instruction and comparand data. The redundant CAM devices each store a duplicate of the data stored in CAM device 107 which results in increased table management by control logic in which system 100 is incorporated.
It would be advantageous to increase the sustained search rate of a CAM device without significantly increasing the table management tasks of a system, and without adding additional redundant (CAM devices.